package com.nowcoder.code.hjnc;

public class NC59 {


    public int minPathSum(int[][] matrix) {
        dfs(matrix, 0, 0);
        return -matrix[0][0] - 1;
    }

    public int dfs(int[][] matrix, int i, int j) {
        if (i < 0 || i == matrix.length | j < 0 || j == matrix[i].length) {
            return -1;
        }

        if (matrix[i][j] < 0) {
            return -matrix[i][j] - 1;
        }
        int r = dfs(matrix, i, j + 1);
        int d = dfs(matrix, i + 1, j);

        int res = matrix[i][j];

        if (r != -1 && d != -1) {
            res = res + Math.min(r, d);
        } else if (r == -1 && d == -1) {

        } else {
            res = res + (r == -1 ? d : r);
        }

        matrix[i][j] = -res - 1;
        return res;
    }

    public static void main(String[] args) {
        int[][] is = {{1, 3, 5, 9}, {8, 1, 3, 4}, {5, 0, 6, 1}, {8, 8, 4, 0}};
        System.out.println(new NC59().minPathSum(is));
    }


}
